An Exact Algorithm for the Maximum Leaf Spanning Tree Problem
Identifieur interne : 000F12 ( Main/Exploration ); précédent : 000F11; suivant : 000F13An Exact Algorithm for the Maximum Leaf Spanning Tree Problem
Auteurs : Henning Fernau [Allemagne] ; Joachim Kneis [Allemagne] ; Dieter Kratsch [France] ; Alexander Langer [Allemagne] ; Mathieu Liedloff [France] ; Daniel Raible [Allemagne] ; Peter Rossmanith [Allemagne]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2009.
Abstract
Abstract: Given an undirected graph G with n nodes, the Maximum Leaf Spanning Tree problem asks to find a spanning tree of G with as many leaves as possible. When parameterized in the number of leaves k, this problem can be solved in time O(4 k poly(n)) using a simple branching algorithm introduced by a subset of the authors [13]. Daligault, Gutin, Kim, and Yeo [6] improved this branching algorithm and obtained a running time of O(3.72 k poly(n)). In this paper, we study the problem from an exact exponential time point of view, where it is equivalent to the Connected Dominating Set problem. For this problem Fomin, Grandoni, and Kratsch showed how to break the Ω(2 n ) barrier and proposed an O(1.9407 n ) time algorithm [10]. Based on some properties of [6] and [13], we establish a branching algorithm whose running time of O(1.8966 n ) has been analyzed using the Measure-and-Conquer technique. Finally we provide a lower bound of Ω(1.4422 n ) for the worst case running time of our algorithm.
Url:
DOI: 10.1007/978-3-642-11269-0_13
Affiliations:
- Allemagne, France
- Centre-Val de Loire, Grand Est, Lorraine (région), Rhénanie-Palatinat, Région Centre
- Metz, Orléans, Trèves (Allemagne)
- Université Paul Verlaine - Metz, Université de Trèves
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001B29
- to stream Istex, to step Curation: 001A12
- to stream Istex, to step Checkpoint: 000459
- to stream Main, to step Merge: 000F86
- to stream Main, to step Curation: 000F12
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">An Exact Algorithm for the Maximum Leaf Spanning Tree Problem</title><author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name><affiliation><country>Allemagne</country><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation></author><author><name sortKey="Kneis, Joachim" sort="Kneis, Joachim" uniqKey="Kneis J" first="Joachim" last="Kneis">Joachim Kneis</name></author><author><name sortKey="Kratsch, Dieter" sort="Kratsch, Dieter" uniqKey="Kratsch D" first="Dieter" last="Kratsch">Dieter Kratsch</name></author><author><name sortKey="Langer, Alexander" sort="Langer, Alexander" uniqKey="Langer A" first="Alexander" last="Langer">Alexander Langer</name></author><author><name sortKey="Liedloff, Mathieu" sort="Liedloff, Mathieu" uniqKey="Liedloff M" first="Mathieu" last="Liedloff">Mathieu Liedloff</name></author><author><name sortKey="Raible, Daniel" sort="Raible, Daniel" uniqKey="Raible D" first="Daniel" last="Raible">Daniel Raible</name></author><author><name sortKey="Rossmanith, Peter" sort="Rossmanith, Peter" uniqKey="Rossmanith P" first="Peter" last="Rossmanith">Peter Rossmanith</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:7BE882E22D197384808B21F7979B89C0EB50025F</idno><date when="2009" year="2009">2009</date><idno type="doi">10.1007/978-3-642-11269-0_13</idno><idno type="url">https://api.istex.fr/document/7BE882E22D197384808B21F7979B89C0EB50025F/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001B29</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001B29</idno><idno type="wicri:Area/Istex/Curation">001A12</idno><idno type="wicri:Area/Istex/Checkpoint">000459</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000459</idno><idno type="wicri:doubleKey">0302-9743:2009:Fernau H:an:exact:algorithm</idno><idno type="wicri:Area/Main/Merge">000F86</idno><idno type="wicri:Area/Main/Curation">000F12</idno><idno type="wicri:Area/Main/Exploration">000F12</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">An Exact Algorithm for the Maximum Leaf Spanning Tree Problem</title><author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Universität Trier, FB 4—Abteilung Informatik, D-54286, Trier</wicri:regionArea><wicri:noRegion>54286, Trier</wicri:noRegion><wicri:noRegion>Trier</wicri:noRegion><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation></author><author><name sortKey="Kneis, Joachim" sort="Kneis, Joachim" uniqKey="Kneis J" first="Joachim" last="Kneis">Joachim Kneis</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Department of Computer Science, RWTH Aachen University</wicri:regionArea><wicri:noRegion>RWTH Aachen University</wicri:noRegion><wicri:noRegion>RWTH Aachen University</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author><author><name sortKey="Kratsch, Dieter" sort="Kratsch, Dieter" uniqKey="Kratsch D" first="Dieter" last="Kratsch">Dieter Kratsch</name><affiliation wicri:level="4"><country xml:lang="fr">France</country><wicri:regionArea>Laboratoire d’Informatique Théorique et Appliquée, Université Paul Verlaine - Metz, 57045, Metz Cedex 01</wicri:regionArea><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Metz</settlement></placeName><orgName type="university">Université Paul Verlaine - Metz</orgName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Langer, Alexander" sort="Langer, Alexander" uniqKey="Langer A" first="Alexander" last="Langer">Alexander Langer</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Department of Computer Science, RWTH Aachen University</wicri:regionArea><wicri:noRegion>RWTH Aachen University</wicri:noRegion><wicri:noRegion>RWTH Aachen University</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author><author><name sortKey="Liedloff, Mathieu" sort="Liedloff, Mathieu" uniqKey="Liedloff M" first="Mathieu" last="Liedloff">Mathieu Liedloff</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>Laboratoire d’Informatique Fondamentale d’Orléans, Université d’Orléans, 45067, Orléans Cedex 2</wicri:regionArea><placeName><region type="region" nuts="2">Centre-Val de Loire</region><region type="old region" nuts="2">Région Centre</region><settlement type="city">Orléans</settlement></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Raible, Daniel" sort="Raible, Daniel" uniqKey="Raible D" first="Daniel" last="Raible">Daniel Raible</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Universität Trier, FB 4—Abteilung Informatik, D-54286, Trier</wicri:regionArea><wicri:noRegion>54286, Trier</wicri:noRegion><wicri:noRegion>Trier</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author><author><name sortKey="Rossmanith, Peter" sort="Rossmanith, Peter" uniqKey="Rossmanith P" first="Peter" last="Rossmanith">Peter Rossmanith</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Department of Computer Science, RWTH Aachen University</wicri:regionArea><wicri:noRegion>RWTH Aachen University</wicri:noRegion><wicri:noRegion>RWTH Aachen University</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2009</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">7BE882E22D197384808B21F7979B89C0EB50025F</idno><idno type="DOI">10.1007/978-3-642-11269-0_13</idno><idno type="ChapterID">13</idno><idno type="ChapterID">Chap13</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: Given an undirected graph G with n nodes, the Maximum Leaf Spanning Tree problem asks to find a spanning tree of G with as many leaves as possible. When parameterized in the number of leaves k, this problem can be solved in time O(4 k poly(n)) using a simple branching algorithm introduced by a subset of the authors [13]. Daligault, Gutin, Kim, and Yeo [6] improved this branching algorithm and obtained a running time of O(3.72 k poly(n)). In this paper, we study the problem from an exact exponential time point of view, where it is equivalent to the Connected Dominating Set problem. For this problem Fomin, Grandoni, and Kratsch showed how to break the Ω(2 n ) barrier and proposed an O(1.9407 n ) time algorithm [10]. Based on some properties of [6] and [13], we establish a branching algorithm whose running time of O(1.8966 n ) has been analyzed using the Measure-and-Conquer technique. Finally we provide a lower bound of Ω(1.4422 n ) for the worst case running time of our algorithm.</div></front></TEI><affiliations><list><country><li>Allemagne</li><li>France</li></country><region><li>Centre-Val de Loire</li><li>Grand Est</li><li>Lorraine (région)</li><li>Rhénanie-Palatinat</li><li>Région Centre</li></region><settlement><li>Metz</li><li>Orléans</li><li>Trèves (Allemagne)</li></settlement><orgName><li>Université Paul Verlaine - Metz</li><li>Université de Trèves</li></orgName></list><tree><country name="Allemagne"><region name="Rhénanie-Palatinat"><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name></region><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name><name sortKey="Kneis, Joachim" sort="Kneis, Joachim" uniqKey="Kneis J" first="Joachim" last="Kneis">Joachim Kneis</name><name sortKey="Kneis, Joachim" sort="Kneis, Joachim" uniqKey="Kneis J" first="Joachim" last="Kneis">Joachim Kneis</name><name sortKey="Langer, Alexander" sort="Langer, Alexander" uniqKey="Langer A" first="Alexander" last="Langer">Alexander Langer</name><name sortKey="Langer, Alexander" sort="Langer, Alexander" uniqKey="Langer A" first="Alexander" last="Langer">Alexander Langer</name><name sortKey="Raible, Daniel" sort="Raible, Daniel" uniqKey="Raible D" first="Daniel" last="Raible">Daniel Raible</name><name sortKey="Raible, Daniel" sort="Raible, Daniel" uniqKey="Raible D" first="Daniel" last="Raible">Daniel Raible</name><name sortKey="Rossmanith, Peter" sort="Rossmanith, Peter" uniqKey="Rossmanith P" first="Peter" last="Rossmanith">Peter Rossmanith</name><name sortKey="Rossmanith, Peter" sort="Rossmanith, Peter" uniqKey="Rossmanith P" first="Peter" last="Rossmanith">Peter Rossmanith</name></country><country name="France"><region name="Grand Est"><name sortKey="Kratsch, Dieter" sort="Kratsch, Dieter" uniqKey="Kratsch D" first="Dieter" last="Kratsch">Dieter Kratsch</name></region><name sortKey="Kratsch, Dieter" sort="Kratsch, Dieter" uniqKey="Kratsch D" first="Dieter" last="Kratsch">Dieter Kratsch</name><name sortKey="Liedloff, Mathieu" sort="Liedloff, Mathieu" uniqKey="Liedloff M" first="Mathieu" last="Liedloff">Mathieu Liedloff</name><name sortKey="Liedloff, Mathieu" sort="Liedloff, Mathieu" uniqKey="Liedloff M" first="Mathieu" last="Liedloff">Mathieu Liedloff</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000F12 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000F12 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:7BE882E22D197384808B21F7979B89C0EB50025F
|texte= An Exact Algorithm for the Maximum Leaf Spanning Tree Problem
}}
| This area was generated with Dilib version V0.6.31. |  |